The present invention relates to geographic data used in navigation systems and more particularly the present invention relates to a way to use geographic data in a navigation system that provides improved performance.
Navigation systems (including navigation applications provided on other types of computing platforms such as general purpose computing platforms) use geographic data. Because navigation systems and navigation applications use geographic data in known ways, the geographic data can be organized and arranged so as to improve the performance of the navigation system or navigation application. Ways that geographic data can be organized and arranged to improve navigation system performance are described in U.S. Pat. Nos. 5,974,419, 5,968,109, and 5,953,722, the entire disclosures of which are incorporated by reference herein.
As described in the aforementioned patents, spatial data are divided into parcels. Each parcel contains data that represent geographic features (e.g., roads, intersections, points of interest, rivers, lakes, etc.) located within a geographic rectangular area. The amount of data in each parcel is constrained not to exceed a specified maximum parcel size. The process of dividing spatial data into parcels is referred to as “parcelization” and data that have been organized into parcels are referred to as being “parcelized.” FIGS. 1–3 show the same geographic data parcelized using different maximum parcel sizes.
Spatially parcelized data are stored on various physical media, such as CD-ROM disks, DVD disks, hard drives, etc. Parcelized geographic data are accessed from such media and used by navigation systems and navigation applications.
Determining the best size to parcelize geographic data involves balancing several different factors. When a navigation system reads data from a medium into the memory of the navigation system (or other computing platform), there is overhead associated with each I/O operation. For example, it takes longer to read two 8K parcels separately from a CD-ROM disk than it does to read one 16K parcel. I/O performance is therefore degraded when average parcel size is too low.
On the other hand, during normal use of a navigation system, it is preferable to maintain several parcels of data in a buffer memory of the system at the same time. Some systems have limited memory resources. This imposes an upper limit on parcel size. If parcels are relatively large compared to the available buffer memory, relatively few parcels can be stored in the buffer memory at one time and therefore parcels may have to be discarded more frequently because the buffer space is needed for a different parcel. However, a discarded parcel may be needed a short time later and therefore the discarded parcel has to be re-read, thereby degrading performance.
Testing or analysis could suggest at what parcel size these two constraints are in balance and I/O performance is optimal. However, the best parcel size may vary from one hardware platform to another. A parcel size that is optimal for one platform could be sub-optimal for a different platform.
Accordingly, there is a need for a way to use geographic data in navigation systems to improve performance.